package haha;

import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-26
 * Time: 22:31
 */
public class HFMS {
    static class Node{
        public Character ch;
        public int freq;
        public Node left;
        public Node right;
        String code;
        public Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public Node(Character ch) {
            this.ch = ch;
        }

        public int getFreq() {
            return freq;
        }
        public boolean isLeaf(){
            return left == null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "ch=" + ch +
                    ", freq=" + freq +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public Map<Character , Node> map =new TreeMap<>();
    public HFMS(String str){
        char[] chs = str.toCharArray();
        for (int i = 0; i <chs.length; i++) {
            if(! map.containsKey(chs[i])){
                map.put(chs[i],new Node(chs[i]));
            }
            Node node = map.get(chs[i]);
            node.freq++;

        }
        for (Node n: map.values()   ) {
            System.out.println(n);
        }


        //构造树
        PriorityQueue<Node > queue = new PriorityQueue<>(Comparator.comparingInt(Node::getFreq));
        queue.addAll(map.values());
        while(queue.size() >= 2){
            Node n1 = queue.poll();
            Node n2 = queue.poll();
            int freq = n1.freq + n2.freq;
            Node node = new Node(freq,n1 ,n2);
            queue.offer(node);
        }
        Node root = queue.poll();
        System.out.println(root);
        //编码
        int sum =  dfs(root , new StringBuilder() );
        for (Node n:   map.values()  ) {
            System.out.println(n.ch + ": " + n.code);
        }
        System.out.println("sum = "+ sum);
    }
    private int dfs(Node root, StringBuilder stringBuilder){
        int sum =0;
        if(root.isLeaf()){
            root.code = stringBuilder.toString();
            sum = root.freq * stringBuilder.length();
        }else{
            sum+=dfs(root.left,stringBuilder.append("0"));
            sum+=dfs(root.right,stringBuilder.append("1"));
        }
        if(stringBuilder.length() >0){
            stringBuilder.deleteCharAt(stringBuilder.length()-1);

        }
        return sum;
    }


    public static void main(String[] args) {
        new HFMS("aabccccc");
    }

}